package Easy.BitOperation;

/**
 * @author: white-zhou
 * @date: 2024-09-18 17:58
 **/
public class CountBits {
    // 原理：i & (i - 1) 可以消去 i 的最后一个 1，因此 ans[i] = ans[i & (i - 1)] + 1
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        ans[0] = 0;
        for (int i = 1; i <= n; i++) {
            ans[i] = ans[i & (i - 1)] + 1;
        }
        return ans;
    }
}
